package mess;

public class LeeCode_86 {
    public static void main(String[] args) {
        System.out.println(partition(new ListNode(1, new ListNode(4,
                new ListNode(3, new ListNode(2, new ListNode(5, new ListNode(2)))))), 3));
        System.out.println(partition(new ListNode(1), 2));
    }
    private static ListNode partition(ListNode head, int x) {
        if (head == null)
            return null;
        ListNode pre = new ListNode(0, head);
        ListNode sml = pre;
        ListNode big = null;
        boolean flag = true;
        boolean flag2 = true;
        ListNode bStat = null;
        ListNode cur = head;
        while(cur != null){
            if(cur.val < x){
                if(flag){
                    pre.next = cur;
                    sml = pre.next;
                    flag = false;
                }else{
                    sml.next = cur;
                    sml = sml.next;
                }
            }else{
                if(flag2){
                    bStat = cur;
                    big = bStat;
                    flag2 = false;
                }else{
                    big.next = cur;
                    big = big.next;
                }
            }
            cur = cur.next;
        }
        if (big != null)
            big.next = null;
        sml.next = bStat;
        return pre.next;
    }
    private static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }

        @Override
        public String toString() {
            return this.val + "->" + next;
        }
    }
}
